package 归并排序;

import java.util.Arrays;

public class 归并排序 {
    public static void merge(int[] arr,int low,int mid,int high) {
        //合并左右区间
        //面试题！！！   合并两个有序数组
        int[] tmp=new int[high-low+1];
        int k=0;//tmp数组的小标
        int s1=low;
        int s2=mid+1;
        int e1=mid;
        int e2=high;

        while (s1<=e1 && s2<=e2) {
            if (arr[s1]<=arr[s2]) {
                //<= 中的"等于" 使得归并排序是稳定的
                tmp[k]=arr[s1];
                k++;
                s1++;
            }else {
                tmp[k++]=arr[s2++];
            }
        }

        while (s1<=e1) {
            //进入该循环，代表左区间留有元素
            tmp[k]=arr[s1];
            k++;
            s1++;
        }
        while (s2<=e2) {
            //进入该循环，代表右区间留有元素
            tmp[k]=arr[s2];
            k++;
            s2++;
        }

        //将归并排好序的数组tmp 重新拷贝到 原数组arr中
        for (int i = 0; i < tmp.length; i++) {
            arr[i+low]=tmp[i];
        }

    }
    public static void mergeSortChild(int[] arr,int low,int high) {
        if (low >= high) {
            return;
        }

        int mid=(low+high)/2;
        mergeSortChild(arr,low,mid);//递归左区间
        mergeSortChild(arr,mid+1,high);//递归右区间

        //归并左右区间
        merge(arr,low,mid,high);

    }

    public static void mergeSort(int[] arr) {
        mergeSortChild(arr,0,arr.length-1);
    }

    public static void main(String[] args) {
        int[] arr={12,5,9,34,6,8,33,56,89,0,7,4,22,55,77};
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));

    }
}
